package com.lry.basic.algorithm.graph;


public class CycleDetection2 {
    private UndirectedGraph graph;
    private boolean[] visited;
    private boolean hasCycle;

    public CycleDetection2(UndirectedGraph graph){
        this.graph = graph;
        visited = new boolean[graph.vertexNum()];
        for(int v=0;v<graph.vertexNum();v++){
            if(!visited[v]){
                if(dfs(v,v)){
                    hasCycle = true;
                    break;
                }
            }
        }
    }
    public boolean isHasCycle(){
        return hasCycle;
    }

    /**
     * v是从parent顶点过来的
     * @param v
     * @param parent
     * @return
     */
    private boolean dfs(int v,int parent){
        visited[v] = true;
        for(int w:graph.adj(v)) {
            if(!visited[w]){
                if(dfs(w,v))return true;
                //0-----1，排除0->1->0这种环检测
            }else if(w!=parent){
                return true;
            }
        }
        return false;
    }


    public static void main(String[] args) {
        UndirectedGraph graph = new UndirectedGraph("graph.txt");
        System.out.println(graph);
        CycleDetection2 graphDFS = new CycleDetection2(graph);
        System.out.println(graphDFS.isHasCycle());
    }
}
